package com.cat.binaryAnswer;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-number-of-seconds-to-make-mountain-height-zero/description/
 * @create 2025/8/11 09:36
 * @since JDK17
 */

public class Solution08 {
    boolean check(int[] workerTimes, int mountainHeight, long target) {
        int sum = 0, n = workerTimes.length;
        for (int i = 0; i < n; i++) {
            int l = -1, r = mountainHeight + 1, mid, k = workerTimes[i];
            while (l + 1 < r) {
                mid = l + (r - l) / 2;
                if ((k + (long)mid * k) * (mid + 1) <= target) {
                    l = mid;
                } else {
                    r = mid;
                }
            }
            sum += l;
        }
        return sum >= mountainHeight;   // 能够移完
    }

    public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {
        int n = workerTimes.length, min = workerTimes[0];
        for (int i = 1; i < n; i++) {
            min = Math.min(min, workerTimes[i]);
        }
        long l = 0, r = (min + (long)min * mountainHeight) * (mountainHeight + 1) / 2, mid;
        while (l + 1 < r) { //
            mid = l + (r - l) / 2;
            if (check(workerTimes, mountainHeight, mid)) {
                r = mid;
            } else {
                l = mid;
            }
        }
        return r;
    }
}
